1. Field of the Invention
The invention pertains to the field of marine navigation and more particularly to the calculation of the geometry of a moving haven along a navigation path.
2. Description of the Prior Art
A moving haven is a mechanism used in marine navigation to manage the voyages of marine vessels. A moving haven is generally a three-dimensional region which moves along a predefined path, a voyage plan. A vessel using a moving haven for navigation may move freely within the region, but may not go outside its boundaries.
The calculation of the geometry of the moving haven presents some difficult challenges due to the subtle variations of its shape for small changes in the parameters that define it. Prior solutions focused on drawing the moving haven in its more common manifestations and required special case logic to handle variations from the norm. Special case logic makes software more complicated, and it is difficult to make complex software work correctly. Furthermore, it is difficult to identify all the special cases, so some are inevitably missed.
A moving haven is a two dimensional region that moves through the ocean. A ship may not cross outside the moving haven boundary, but is allowed to operate within it freely.
A moving haven, in its simplest manifestation, is a rectangle. As it progresses through the water, it follows a predefined path, which is called a voyage plan, defined by a series of waypoints connected by legs. A rectangular buffer, the sides of which are a predetermined distance from the corresponding sides of the rectangle, provides an early warning to the navigator that the ship is approaching the edge of the moving haven.
As the name implies, the moving haven is in motion. When it approaches a waypoint it must turn from one leg to the next. When a rectangular moving haven spans a waypoint, the region that the moving haven encompasses generally includes the area of two overlapping rectangles and one pie slice shaped region, as shown in Figure P1. The first rectangle is defined around the line segment starting at the intersection of the trailing edge and voyage plan leg AB and ending at waypoint B. The second rectangle is defined around the line segment starting at waypoint B and ending at the intersection of the leading edge and the voyage plan leg BC. The pie slice shaped region, having an arc center at B, fills in the gap between the two rectangles.
Determining the geometry for the moving haven boundary must be accompanied by the determination of the geometry of the moving haven buffer. The moving haven buffer must be drawn so that each point on the buffer is exactly a predetermined distance from at least one point on the moving haven boundary, and no closer than the predetermined distance to any point on the moving haven boundary. It would be expected that the boundary has the same shape of the moving haven, but drawn smaller. This, however, is not the case. Often, when the moving haven has a sharp turn, the buffer requires a smooth curve, as shown in Figure P2.
Calculating the geometry of the moving haven boundary and its buffer is a difficult problem that has challenged engineers for years. The difficulties are a result of A) the moving haven often taking form of a variety of shapes and B) the fact that the buffer and boundary are not proportional, e.g. the buffer is, not simply a smaller rendition of the boundary.
Past attempts to determine the moving haven geometry have resulted in only marginal success, partially do to the following:                A) The problem was not decomposed adequately into smaller more manageable sub-problems.        B) Special case logic was required to handle irregular geometries.        C) No single solution was found to solve both the boundary problem and the buffer problem.        
Past solutions have constructed the moving haven geometry sequentially, starting at some vertex on the boundary (or buffer) and working either clockwise or counter clockwise, determining subsequent vertices in the order that they appear in the final geometry. Such solutions also attempted to construct the boundary directly from the voyage plan geometry, rather than constructing intermediate results, and then making further refinements to arrive at the final geometry. The following is an example of a method that calculates the geometry sequentially.
Refer to Figure P3, assume P is the intersection of the trailing edge and the first leg, Q is the waypoint that the moving haven spans, and R is the intersection of the leading edge and the second leg. The moving haven boundary is shown with dark solid lines. The buffer is shown with a dotted line.                1) Point A is found by adding to point P a vector perpendicular to PQ of length equal to half the width of the moving haven.        2) Point B is found by adding to point Q a vector perpendicular to PQ of length equal to half the width of the moving haven.        3) Points are calculated to form an arc between B and C. The arc has a radius equal to half the width of the moving haven.        4) Point C is found by adding to point Q a vector perpendicular to QR of length equal to the half width of the moving haven.        5) Point D and E and found in a similar fashion.        6) A temporary line EH is found by shifting QR in a direction perpendicular to QR a distance equal to half of the moving haven width. A temporary line GI is found by shifting PQ in a direction perpendicular to PQ a distance equal to the half of the moving haven width. Point F is the intersection of these two lines.        7) Point G is found in a way similar to point A.        
Notice that the steps outlined above are very specific to calculating a moving haven spanning a single waypoint as shown in FIG. 5. Because the steps are specific to this particular scenario, a modification to these steps is required if the scenario changes in subtle ways. Furthermore, additional logic is required to detect that the scenario has changed. The following illustrates a few alternate scenarios and the difficulties these variations introduce.
As with the moving haven in Figure P3, the moving haven in Figure P4 spans a single waypoint. But this scenario differs in that the leading edge has just past a waypoint. As a result, the leading edge is not drawn in full. A portion of the leading edge is clipped by the area of the moving haven drawn around the first leg. Because the steps outlined above provide no provision for the leading edge being clipped, special case logic is required to detect this situation and account for its differences appropriately.
Figure P5 shows yet another scenario that requires special case logic. In this case, the leading edge is partitioned into two sections, because it intersects a portion of the moving haven that spans the first leg.
The above examples demonstrate the need for special case logic when the moving haven spans a single waypoint. It may be possible to identify and handle all special cases for the single waypoint situation, but the number of special cases becomes unmanageable when the moving haven spans two or more waypoints. As shown in Figure P6, the moving haven geometry can become quite complex when spanning as few as two waypoints. Determining the special case logic to calculate the boundary geometry for this shape directly from the voyage plan is difficult and likely to be error prone.
The above discussion focused on the difficulties in drawing the moving haven boundary. Calculating the moving haven buffer suffers from these and additional difficulties, making buffer problem harder to solve.
Prior art software fails, in many situations, to calculate the boundary and buffer geometries for the following reasons:                A) Prior art solutions did not adequately divide the problem into small simple sub-solutions, attempting to solve the entire problem at once. These programs attempted to calculate the final geometry directly from the voyage plan geometry.        B) Special case logic was required for handling variations in the voyage plan geometry.        C) Two separate methods were required for calculating the boundary and the buffer, resulting in more opportunities for errors to be introduced.        